package algorithm;

public class leetcode_0337 {
    public int rob(TreeNode root) {
        int[] robHelp = robHelper(root);
        //取偷根节点和不偷根节点的最大值
        return Math.max(robHelp[1], robHelp[0]);

    }
    public int[] robHelper(TreeNode root) {
        //边界条件
        if (root == null)
           return new int[2];
         //这里的left是个长度为2的一维数组，其中left[0]表示不偷root.left节点
         //所能偷窃的最大金额，left[1]表示偷root.left节点所能偷窃的最大金额。
         int[] left = robHelper(root.left);
         //right节点同left
         int[] right = robHelper(root.right);
         //Math.max(right[0], right[1]), root.val + left[0] + right[0]表示
         //的是不能偷当前节点，所以可以偷两个子节点，也可以不偷子节点，我们取最大的。
         //root.val + left[1] + right[1]表示的是偷当前节点，所以不能偷两个子节点。
         return new int[]{Math.max(left[0], left[1]) +
               Math.max(right[0], right[1]), root.val + left[0] + right[0]};
         }

}
